package com.gitee.feizns.explore.data_structure.linked_list.singly.flatten;

/**
 * 扁平化多级双向链表
 * 您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 * <p>
 * 扁平化列表，使所有结点出现在单级双链表中。您将获得列表第一级的头部。
 *
 * @author feizns
 * @since 2019/10/9
 */
public class Flatten {

    public static void main(String[] args) {
        Node node = create();
        node.print();
        flatten(node).print();
    }

    public static Node flatten(Node head) {
        if ( head != null )
            flattenReturnLast(head);
        return head;
    }

    public static Node flattenReturnLast(Node head) {
        if ( head.child != null ) {
            Node next = head.next;
            Node last = flattenReturnLast(head.child);
            head.next = head.child;
            head.child.prev = head;
            head.child = null;
            if ( next != null ) {
                last.next = next;
                next.prev = last;
                return flattenReturnLast(next);
            }
            return last;
        }
        return head.next == null ? head : flattenReturnLast(head.next);
    }

//    public static Node flatten(Node head) {
//        Node ret = head;
//        if ( ret != null )
//            flattenReturnLast(ret);
//        return ret;
//    }
//
//
//
//    private static Node flattenReturnLast(Node head) {
//        while (head.next != null || head.child != null) {
//            if (head.child != null) {
//                Node next = head.next;
//                head.next = head.child;
//                head.child.prev = head.next;
//                head.child = null;
//                Node last = flattenReturnLast(head.next);
//                last.next = next;
//                if (next != null)
//                    next.prev = last;
//                return flattenReturnLast(last);
//            }
//            head = head.next;
//        }
//        return head;
//    }

    private static Node create() {
        Node node = new Node(1);
        node.setNext(new Node(2));
        node.next.setNext(new Node(3));
        node.next.next.child = create1();
        node.next.next.setNext(new Node(4));
        node.next.next.next.setNext(new Node(5));
        return node;
    }

    private static Node create1() {
        Node ret = new Node(7);
        ret.setNext(new Node(8));
        ret.next.child = create2();
        ret.next.setNext(new Node(9));
        ret.next.next.setNext(new Node(10));
        return ret;
    }

    private static Node create2() {
        Node ret = new Node(11);
        ret.setNext(new Node(12));
        return ret;
    }

}
